package cn.z2huo.algorithm.dynamicprogramming.backpack;
/*
* 使用动态规划算法解决0-1背包问题
*
* 0-1背包问题与背包问题的区别：
* 前者中的物品要不放进去，要不不放进去，不能放一个物体的一部分
* 后者，一个物品可以放进去，可以不放进去，也可以只放进去该物体的一部分
*
* */
public class Main {
    // 算法主体，自底向上，计算最优解。原问题的最优包含子问题的最优。
    public void resolve(int[] weight, int[] value, int[][] result, int capacity){
        // 用来判断最后一个物体是否可以放得下，如果可以放得下，就将物体放入，之后修改结果数组
        for(int j=0; j<capacity+1; j++){    // 从容量为0时，开始遍历，知道容量最大时
            if(j >= weight[weight.length-1]){
                result[weight.length-1][j] = value[weight.length-1];
            }else{
                result[weight.length-1][j] = 0;
            }
        }

        // 从倒数第二个物体向上判断
        for(int i=result.length-2; i>=0; i--){
            // 从容量为0时候遍历，知道容量到达最大
            for(int j=0; j<result[i].length; j++){
                // 如果现有的容量大于等于该物体的重量，则判断是否可以放下更多东西
                if(j >= weight[i]){
                    // 判断 该物体的价值加上放入该物体后余下容量的价值 与 结果数组中下一个物体在此容量下的价值 的关系，之后赋值
                    result[i][j] = result[i+1][j]>result[i+1][j-weight[i]]+value[i] ? result[i+1][j] : result[i+1][j-weight[i]]+value[i];
                // 如果现有容量小于该物体的重量，则此时应与该物体之后的物体的结果相同（依次向后判断）
                }else {
                    result[i][j] = result[i+1][j];
                }
            }
        }
    }

    // 用来初始化二维数组
    public void initArray(int[][] array, int num){
        for(int i=0; i<array.length; i++){
            for(int j=0; j<array[i].length; j++){
                array[i][j] = num;
            }
        }
    }
    // 用来打印输出二维数组
    public void printArray(int[][] array){
        for(int i=0; i<array.length; i++){
            for(int j=0; j<array[i].length; j++){
                System.out.printf("%3d", array[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args){
        int capacity = 5;
        int[] weight = {2, 1, 3, 2};
        int[] value = {12, 10, 20, 15};
//        int capacity = 10;
//        int[] weight = {2, 2, 6, 5, 4};
//        int[] value = {6, 3, 5, 4, 6};
        int[][] result = new int[weight.length][capacity+1];

        Main m = new Main();
        m.initArray(result, 0);
        m.resolve(weight, value, result, capacity);
        m.printArray(result);
        System.out.println("最大的价值是：");
        System.out.println(result[0][capacity]);
        System.out.println("放入的物体是：");
    }
}